package Leetcode.数组字符串;

/**
 * @Author kirito
 * @Date 2023/10/30 9:37
 * @PackageName:Leetcode.数组字符串
 * @ClassName: H指数2
 * @Description:
 * 给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数，citations 已经按照 升序排列 。计算并返回该研究者的 h 指数。
 *
 * h 指数的定义：h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （n 篇论文中）总共有 h 篇论文分别被引用了至少 h 次。
 *
 * 请你设计并实现对数时间复杂度的算法解决此问题。
 *
 *
 *
 * 示例 1：
 *
 * 输入：citations = [0,1,3,5,6]
 * 输出：3
 * 解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 0, 1, 3, 5, 6 次。
 *      由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3 。
 * 示例 2：
 *
 * 输入：citations = [1,2,100]
 * 输出：2
 * @Version 1.0
 */
public class H指数2 {
    /*
    * 方法一：二分查找
由于数组 citations 已经按照升序排序，因此可以使用二分查找。

设查找范围的初始左边界 left 为 0, 初始右边界 right 为 n−1，其中 n 为数组 citations 的长度。每次在查找范围内取中点 mid，则有 n−mid 篇论文被引用了至少 citations[mid] 次。
* 如果在查找过程中满足 citations[mid]≥n−mid，则移动右边界 right，否则移动左边界 left。
*/
    public int hIndex(int[] citations) {
        int n = citations.length; // 获取引用数组的长度
        int left = 0, right = n - 1; // 初始化左右指针，左指针指向数组的起始位置，右指针指向数组的结束位置
        while (left <= right) { // 使用二分查找法，当左指针小于等于右指针时进行循环
            int mid = left + (right - left) / 2; // 计算中间位置的索引
            if (citations[mid] >= n - mid) { // 如果中间位置的引用大于等于剩余的论文数量
                right = mid - 1; // 将右指针移动到中间位置的左边一位
            } else {
                left = mid + 1; // 否则将左指针移动到中间位置的右边一位
            }
        }
        return n - left; // 返回H指数，即总论文数量减去左指针的位置
    }
}
